package leetcode.p138;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: trtan
 * @date: 2021-07-22 14:30
 **/
public class CopyListWithRandomPointer {
    /**
     * 复制带随机指针的链表，记录原链表每个节点的位置，那么建立新链表时更加位置确定随机指针的指向。
     * @param head
     * @return leetcode.p138.Node
     * @author trtan
     * @date 2021/7/22 15:02
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        List<Node> list = new ArrayList<>();
        // 映射，原链表node对应的下标，和下标对应的node
        Map<Node, Integer> map = new HashMap<>(16);
        Map<Integer, Node> rMap = new HashMap<>(16);
        Node root = new Node(-1);
        Node tmp = head;
        Node pre = root;
        int i = 0;
        while (tmp != null) {
            Node node = new Node(tmp.val);
            pre.next = node;
            pre = node;

            list.add(node);

            map.put(tmp, i);
            rMap.put(i, tmp);

            i++;
            tmp = tmp.next;
        }
        for (int j = 0; j < list.size(); j++) {
            Node node = list.get(j);
            // 根据第j个链表的random对应的下标获取node
            Node r = rMap.get(j).random;
            if (r != null) {
                int k = map.get(r);
                System.out.println(k);
                Node random = list.get(k);
                node.random = random;
            } else {
                node.random = null;
            }
        }
        return root.next;
    }


    Map<Node, Node> cache = new HashMap<>(16);

    /**
     * 方法二 记忆化搜索
     * dfs遍历链表，递归为每个节点的next和random赋值
     * 每遍历到一个节点，记录原链表节点和新链表节点的对应关系
     * 可以用一个map作为缓存，记录节点是否出现过
     * @param head
     * @return leetcode.p138.Node
     * @author trtan
     * @date 2021/7/22 15:05
     */
    public Node copyRandomList2(Node head) {
        if (head == null) {
            return null;
        }
        if (!cache.containsKey(head)) {
            Node node = new Node(head.val);
            cache.put(head, node);
            node.next = copyRandomList2(head.next);
            node.random = copyRandomList2(head.random);
        }
        return cache.get(head);
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}